package com.bolang.onlycode.demo;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RaidxSort {


    public static void main(String[] args) {
        int[] arr={170, 45, 75, 90, 802, 24, 2, 66};
        int n = arr.length;
        radixSort(arr, n);
        System.out.println(Arrays.toString(arr));
    }
    public static int getMax(int arr[],int n){
        int max=arr[0];
        for(int i=0;i<n;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        return max;
    }
    static void countSort(int arr[], int n, int exp) {
        int output[] = new int[n]; //输出数组
        int i;
        int count[] = new int[10];
        Arrays.fill(count, 0);

        // 统计数组中元素第 exp 位的数目
        for (i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // 对 count[] 数组进行转
        for (i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 进行计数排序
        for (i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 输出到数组arr[]中
        for (i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    public static void radixSort(int[] arr,int n){
        int m=getMax(arr,n);
        // 对数组当中的数字按照每一个有效位进行一趟计数排序。
        for (int exp = 1; m/exp > 0; exp *= 10){
            countSort(arr, n, exp);
        }
    }


}
